package dfs;
//一个数独的解法需遵循如下规则：
//
//    数字 1-9 在每一行只能出现一次。
//    数字 1-9 在每一列只能出现一次。
//    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
//
//空白格用 '.' 表示。

public class 解数组 {
    public static void main(String[] args) {

    }
    public static void solveSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] boxs = new boolean[9][9];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j]=='.')
                    continue;
                else{
                     int num=board[i][j]-'1';
                     rows[i][num]=cols[j][num]=boxs[(i/3)*3+j/3][num]=true;
                }
            }
            solveSudokuHelper(board,0,rows,cols,boxs);
        }
    }
    private static boolean solveSudokuHelper(char[][] board, int n, boolean[][] rows, boolean[][] cols, boolean[][] boxs) {
       if (n==81)
           return true;
       int i=n/9;
       int j=n%9;
       int k=i/3*3+j/3;
       if (board[i][j]!='.')
           solveSudokuHelper(board,n+1,rows,cols,boxs);
    //填充数独
        for (int num = 0; num < 9; num++) {
            //如果存在这个值，跳过循环
           if (rows[i][num] || cols[j][num] || boxs[k][num])
               continue;
           board[i][j]=(char) (num+'1');
           rows[i][num] = cols[j][num] = boxs[k][num]=true;
           if (solveSudokuHelper(board,n+1,rows,cols,boxs))
               return true;
           rows[i][num]=cols[j][num]=boxs[k][num]=false;
        }
        //填充错误，从新开始
         board[i][j]='.';
         return false;
    }
}
